Увидел у Игоря Викторовича в vk отличный пост: https://vk.com/wall137669108_516

Problem

Simple solution in continuous space


In [1]:
import scipy.optimize
import numpy as np
import pandas as pd

In [2]:
gold = int(2 * 1e5)
gems = 115
mercury = 80
distant_min_health = 4000
air_min_health = 2000
gem_price = 500

In [3]:
units = [
    {'name': 'titan', 'health': 300, 'gold': 5000, 'mercury': 1, 'gems': 3, 'available': 10},
    {'name': 'naga', 'health': 120, 'gold': 1500, 'mercury': 0, 'gems': 2, 'available': 20},
    {'name': 'djinn', 'health': 60, 'gold': 750, 'mercury': 1, 'gems': 1, 'available': 30},
    {'name': 'mage', 'health': 40, 'gold': 500, 'mercury': 1, 'gems': 1, 'available': 55},
    {'name': 'golem', 'health': 35, 'gold': 400, 'mercury': 1, 'gems': 0, 'available': 60},
    {'name': 'gargoyle', 'health': 20, 'gold': 200, 'mercury': 0, 'gems': 0, 'available': 110},
    {'name': 'gremlin', 'health': 4, 'gold': 70, 'mercury': 0, 'gems': 0, 'available': 500},
]
distant = ['titan', 'mage', 'gremlin']
air = ['djinn', 'gargoyle']
units = pd.DataFrame(units)
units.index = units.name
units['distant'] = 0
units['air'] = 0
units.loc[distant, 'distant'] = 1
units.loc[air, 'air'] = 1
units


Out[3]:
available gems gold health mercury name distant air
name
titan 10 3 5000 300 1 titan 1 0
naga 20 2 1500 120 0 naga 0 0
djinn 30 1 750 60 1 djinn 0 1
mage 55 1 500 40 1 mage 1 0
golem 60 0 400 35 1 golem 0 0
gargoyle 110 0 200 20 0 gargoyle 0 1
gremlin 500 0 70 4 0 gremlin 1 0

X = [Titan, Naga, Djinn, Mage, Golem, Gargoyle, Gremlin, Sold gems]


In [4]:
loss_function = -np.hstack([units.health, [0]])
A = [(-units.health * units.distant).tolist() + [0],
     (-units.health * units.air).tolist() + [0],
     units.mercury.tolist() + [0],
     units.gems.tolist() + [1],
     units.gold.tolist() + [-gem_price]]
b = [-distant_min_health, -air_min_health, mercury, gems, gold]
bounds = [(0, available) for available in units.available] + [(0, gems)]

In [5]:
%%time
result = scipy.optimize.linprog(loss_function, A, b, bounds=bounds)


CPU times: user 14.9 ms, sys: 4.46 ms, total: 19.4 ms
Wall time: 17.1 ms

Решение найдено почти мгновенно.


In [6]:
result


Out[6]:
     fun: -12875.0
 message: 'Optimization terminated successfully.'
     nit: 13
   slack: array([  1600.,   2000.,  23000.,      0.,      0.,      0.,     40.,
            0.,      0.,     35.,    115.,      0.,      0.])
  status: 0
 success: True
       x: array([  10.,   20.,   30.,   15.,   25.,  110.,  500.,    0.])

Последний элемент ответа 0 - камни продавать не нужно. Сила набранной армии: 12875.

Сила существ дальнего боя / воздушной армии:


In [7]:
-np.dot(result.x, np.array(A[0])), -np.dot(result.x, A[1])


Out[7]:
(5600.0, 4000.0)

Затраченные ресурсы:


In [8]:
np.dot(result.x, A[2]), np.dot(result.x, A[3]), np.dot(result.x, A[4])


Out[8]:
(80.0, 115.0, 177000.0)

Ртуть и камни потратили полностью, монеты еще остались.

Внимательный читатель мог заметить, что решение не совсем честное. Задачу я увидел уже глубокой ночью и воспользовался тем инструментом, что уже знал. Так повезло, что найденное решение оказалось целочисленным. Но вообще, это не всегда так. Вот результат для задачи с такими же условиями, но когда у Дениса только 100k золота:


In [10]:
result.x


Out[10]:
array([   6.66666667,   13.26666667,    0.        ,    0.        ,
         60.        ,  110.        ,  500.        ,   68.46666667])

Для общего случая ILP дальше не всегда можно просто докрутить до целых чисел. А это прекрасный повод забыть про родной L-BFGS и окунуться в мир целочисленных линейных задач.

Integer Linear Problem

Вообще, известно как с помощью дополняющих условий (Cutting-plane method) сводить задачу к целочисленной, но делать это на scipy не стоит.

Я начал копать с этой страницы: http://prod.sandia.gov/techlib/access-control.cgi/2013/138847.pdf И остановился сразу как только нашел слово GNU. Интересно, что основатель проекта из МАИ. Список python биндингов: https://en.wikibooks.org/wiki/GLPK/Python


In [11]:
import pulp

In [12]:
problem = pulp.LpProblem("Heroes III", pulp.LpMaximize)

In [13]:
titan = pulp.LpVariable('titan', lowBound=0, upBound=units.loc['titan'].available, cat='Integer')
naga = pulp.LpVariable('naga', lowBound=0, upBound=units.loc['naga'].available, cat='Integer')
djinn = pulp.LpVariable('djinn', lowBound=0, upBound=units.loc['djinn'].available, cat='Integer')
mage = pulp.LpVariable('mage', lowBound=0, upBound=units.loc['mage'].available, cat='Integer')
golem = pulp.LpVariable('golem', lowBound=0, upBound=units.loc['golem'].available, cat='Integer')
gargoyle = pulp.LpVariable('gargoyle', lowBound=0, upBound=units.loc['gargoyle'].available, cat='Integer')
gremlin = pulp.LpVariable('gremlin', lowBound=0, upBound=units.loc['gremlin'].available, cat='Integer')
sold_gems = pulp.LpVariable('sold gems', lowBound=0, upBound=gems, cat='Integer')
army = [titan, naga, djinn, mage, golem, gargoyle, gremlin]

In [14]:
# gain function
problem += np.dot(army, units.health.values)

In [15]:
# restrictions
problem += np.dot(army, units.health * units.distant) >= distant_min_health
problem += np.dot(army, units.health * units.air) >= air_min_health
problem += np.dot(army, units.mercury) <= mercury
problem += np.dot(army + [sold_gems], units.gems.tolist() + [1]) <= gems
problem += np.dot(army + [sold_gems], units.gold.tolist() + [-gem_price]) <= gold

In [16]:
%%time
pulp.LpStatus[problem.solve()]


CPU times: user 2.4 ms, sys: 7.2 ms, total: 9.6 ms
Wall time: 23.5 ms
Out[16]:
'Optimal'

In [17]:
solution = pd.DataFrame([{'value': parameter.value()} for parameter in problem.variables()],
                        index=[parameter.name 
                               for parameter in problem.variables()])
solution.loc[['sold_gems'] + units.name.tolist()]


Out[17]:
value
sold_gems 69.0
titan 7.0
naga 6.0
djinn 13.0
mage 0.0
golem 60.0
gargoyle 110.0
gremlin 496.0

Теперь пришлось продавать камни.


In [18]:
optimal_army = [unit.value() for unit in army]

Дальнобойные, воздушные


In [19]:
np.dot(optimal_army, units.health * units.distant), np.dot(optimal_army, units.health * units.air)


Out[19]:
(4084.0, 2980.0)

Затраченные ресурсы


In [20]:
np.dot(optimal_army, units.mercury), \
    np.dot(optimal_army + [sold_gems.value()], units.gems.tolist() + [1]), \
    np.dot(optimal_army + [sold_gems.value()], units.gold.tolist() + [-gem_price]), \


Out[20]:
(80.0, 115.0, 99970.0)